/*
    http://bhepple.freeshell.org

    Copyright (C) 2010 Bob Hepple <bhepple@freeshell.org>

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; see the file COPYING.  If not, write to
    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.

*/

/**
 * \file tbd.c
 */

#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <tbd.h>

/* return pointer to tbd if input is OK; else NULL */
static tbd check_tbd(const tbd dlist)
{
    tbd retval = dlist;
    if (dlist) {
        if ((dlist->sentinel1 != SENTINEL) ||
            (dlist->sentinel2 != SENTINEL)) {
            retval = NULL;
        }
    }
    return(retval);
}

tbd tbd_new(size_t                width,
            tbd_free_callback_t   free_callback,
            tbd_create_callback_t create_callback,
            tbd_copy_callback_t   copy_callback,
            void *                callback_data)
{
    tbd retval = NULL;
    
    if ( (retval = (tbd) xcalloc(1, sizeof(struct tbd_s))) ) {
        retval->sentinel1       = SENTINEL;
        retval->width           = width;
        retval->free_callback   = free_callback;
        retval->create_callback = create_callback;
        retval->copy_callback   = copy_callback;
        retval->callback_data   = callback_data;
        retval->first           = NULL;
        retval->sentinel2       = SENTINEL;
    }
    return(retval);
}

void tbd_free(tbd *dlist_in)
{
    if ( dlist_in && check_tbd(*dlist_in) ) {
        tbd dlist = *dlist_in;
        tbd_item iterator = NULL;
        tbd_item next = NULL;

        for (iterator = dlist->first; 
             iterator; 
             iterator = next) {
            next = iterator->next;
            if (dlist->free_callback) {
                iterator->payload = (*(dlist->free_callback))(iterator->payload,
                        dlist->callback_data);
            }
            if (iterator->payload && dlist->width > 0) {
                xfree(iterator->payload);
            }
            xfree(iterator);
        }
        xfree(dlist);
        *dlist_in = NULL;
    }
}

int tbd_get_len(const tbd dlist_in)
{
    int retval = -1;
    tbd dlist;
    
    if ( (dlist = check_tbd(dlist_in)) ) {
        tbd_item iterator = NULL;
        retval = 0;
        for (iterator = dlist->first; 
             iterator; 
             iterator = iterator->next) {
            retval++;
        }
    }
    return(retval);
}

tbd_item tbd_get_next(const tbd_item item)
{
    tbd_item retval = NULL;

    if (item) retval = item->next;
    return(retval);
}

tbd_item tbd_get_prev(const tbd_item item)
{
    tbd_item retval = NULL;

    if (item) retval = item->prev;
    return(retval);
}

tbd_item tbd_get_index(const tbd dlist, size_t num)
{
    int pos;
    tbd_item retval = NULL;

    if ( check_tbd(dlist) ) {
        for (pos = 0, retval = dlist->first; 
             retval && pos < num; 
             retval = retval->next, pos++);
    }
    return(retval);
}

tbd_item _tbd_item_new()
{
    return(xcalloc(1, sizeof(struct tbd_item_s)));
}

/**
 * Internal function to create an empty item on the dlist - assumes
 * check_tbd has already been called.
 */
tbd_item _tbd_append_new(tbd dlist, tbd_item location)
{
    tbd_item retval = NULL;
    
    retval = _tbd_item_new();

    if (location == NULL) {
        // append to the start of the list:
        retval->next = dlist->first;
        if (dlist->first) dlist->first->prev = retval;
        dlist->first = retval;
    } else {
        retval->next = location->next;
        retval->prev = location;
        location->next = retval;

        if (retval->next) {
            retval->next->prev = retval;
        }
    }
    return(retval);
}

tbd_item tbd_append_new(tbd *dlist_in, tbd_item location)
{
    tbd_item retval = NULL;
    void *a;
    tbd_item item = NULL;
    tbd dlist = NULL;
    
    if (dlist_in == NULL) goto end;

    if (*dlist_in == NULL) {
        dlist = tbd_new(0, NULL, NULL, NULL, NULL);
    } else {
        if ( (dlist = check_tbd(*dlist_in)) == NULL) goto end;
    }
        
    item = _tbd_append_new(dlist, location);
    
    if (dlist->width) {
        item->payload = xcalloc(1, dlist->width);
    }
    if (dlist->create_callback) {
        a = (*(dlist->create_callback))(item->payload,
                                        dlist->callback_data);
        if (a && a != item->payload) {
            if (item->payload) xfree(item->payload);
        }
        item->payload = a;
    }

    *dlist_in = (tbd)dlist;
    retval = item;
    
end:
    return(retval);
}

tbd _for_each(tbd                   dlist,
              tbd_item              start_location,
              tbd_item              end_location,
              int                   num,
              tbd_worker_callback_t callback,
              void *                callback_data)
{
    tbd_item next = NULL;
    tbd_item item = NULL;
    int counter = abs(num);
    tbd retval = NULL;
    
    if (num == 0) counter = 1;
    
    if (dlist) {
        if (start_location == NULL) {
            // if num < 0, walk back from the end; else walk forward from the start:
            start_location = dlist->first;
            if (num < 0) {
                // walk to the end:
                for (next = dlist->first; next; next = next->next) {
                    start_location = next;
                }
            }
        }
        
        for (item = start_location; item && counter > 0; item = next) {
            if (end_location && item == end_location) break;
            if (num >= 0) {
                next = item->next;
            } else {
                next = item->prev;
            }
            if ((*callback)(dlist, item, callback_data) == NULL) goto end;
            if (end_location == NULL && num != 0) counter--;
        }
        retval = dlist;
    }
end:
    return (retval);
}

tbd tbd_for_each(tbd                   dlist,
                 tbd_item              start_location,
                 tbd_item        end_location,
                 int                   num,
                 tbd_worker_callback_t callback,
                 void *                callback_data)
{
    tbd retval = NULL;
    
    if ( check_tbd(dlist) ) {
        retval = _for_each(dlist, start_location, end_location,
                           num, callback, callback_data);
    }
    return(retval);
}

/**
 * Internal function to copy just the base elements of a dlist ie not
 * the list itself
 */
static tbd _tbd_copy(const tbd dlist)
{
    return(tbd_new(dlist->width,
                   dlist->free_callback,
                   dlist->create_callback,
                   dlist->copy_callback,
                   dlist->callback_data));
}

void *_for_each_delete_item(tbd      dlist_in,
                            tbd_item location,
                            void *   callback_data_in)
{
    tbd   dlist   = NULL;
    void *retval  = NULL;
    
    if ( (dlist = check_tbd(dlist_in)) ) {
        // _for_each only gives us non-NULL locations:
        if (dlist->first == location) {
            dlist->first = location->next;
            if (dlist->first) dlist->first->prev = NULL;
        } else {
            assert(location->prev != NULL);
            location->prev->next = location->next;
            if (location->next) location->next->prev = location->prev;
        }
        if (location->payload && dlist->free_callback) {
            location->payload = (*(dlist->free_callback))(location->payload, dlist->callback_data);
        }
        if (location->payload) xfree(location->payload);
        xfree(location);
        retval = (void *) 1;
    }
    return(retval);
}

tbd tbd_delete_items(tbd      dlist_in,
                     tbd_item start_location,
                     tbd_item end_location,
                     size_t   num)
{
    tbd dlist;
    tbd retval = NULL;

    if ( (dlist = check_tbd(dlist_in)) ) {
        retval = (tbd) _for_each(dlist, start_location, end_location,
                                 num, _for_each_delete_item, NULL);
    }
    return(retval);
}

void *_for_each_chop_item(tbd      dlist_in,
                          tbd_item location,
                          void *   callback_data_in)
{
    tbd dlist  = NULL;
    tbd_item retval = NULL;
    tbd dest   = (tbd) callback_data_in;
    
    if ( (dlist = check_tbd(dlist_in)) ) {
        // _for_each only gives us non-NULL locations:
        assert(location);
        // unlink from the source dlist:
        if (dlist->first == location) {
            dlist->first = location->next;
            if (dlist->first) dlist->first->prev = NULL;
        } else {
            assert(location->prev != NULL);
            location->prev->next = location->next;
            if (location->next) location->next->prev = location->prev;
        }

        retval = tbd_push((tbd *)&dest, location->payload);
        xfree(location);
    }
    return((void *)retval);
}

tbd tbd_chop_items(tbd            dlist_in,
                   tbd_item       start_location,
                   tbd_item       end_location,
                   int            num)
{
    tbd dlist;
    tbd retval = NULL;
    
    if ( (dlist = check_tbd(dlist_in)) ) {
        retval = _tbd_copy(dlist);
        if ((tbd) _for_each(dlist, start_location, end_location,
                            num, _for_each_chop_item,
                            (void *)retval) == NULL) {
            xfree(retval);
            retval = NULL;
        }
    }
    return(retval);
}

typedef struct copy_callback_data_s {
    tbd      d_dlist;
    tbd_item d_location;
} *copy_callback_data;

void *_for_each_copy_item(tbd      dlist_in,
                          tbd_item location,
                          void *   data_in)
{
    tbd dlist  = NULL;
    void *   retval = NULL;
    copy_callback_data data = (copy_callback_data) data_in;
    void *a;
    
    if ( (dlist = check_tbd(dlist_in)) ) {
        // _for_each only gives us non-NULL locations:
        data->d_location = _tbd_append_new(data->d_dlist, data->d_location);
        if (data->d_dlist->width) {
            data->d_location->payload = xcalloc(1, data->d_dlist->width);
        }
        if (data->d_dlist->copy_callback) {
            a = (*(data->d_dlist->copy_callback))(data->d_location->payload,
                                                 location->payload,
                                                 data->d_dlist->callback_data);
            if (a && a != data->d_location->payload) {
                if (data->d_location->payload) xfree(data->d_location->payload);
            }
            data->d_location->payload = a;
        }
        retval = data->d_location;
    }
    return(retval);
}

tbd tbd_copy_items(tbd            d_dlist_in,
                   tbd_item       d_location_in,
                   const tbd      s_dlist_in,
                   const tbd_item start_location,
                   const tbd_item end_location,
                   int            num)
{
    tbd                         d_dlist;
    tbd                         s_dlist;
    tbd_item                    d_location;
    tbd                         retval = NULL;
    struct copy_callback_data_s callback_data;
    
    if ( (s_dlist = check_tbd(s_dlist_in)) ) {
        d_location = d_location_in;
        if ( (d_dlist = check_tbd(d_dlist_in)) == NULL ) {
            d_dlist = _tbd_copy(s_dlist);
            d_location = NULL;
        } else {
            if (s_dlist->copy_callback != d_dlist->copy_callback ||
                s_dlist->create_callback != d_dlist->create_callback ||
                s_dlist->free_callback != d_dlist->free_callback)
                goto end;
        }

        callback_data.d_dlist = d_dlist;
        callback_data.d_location = d_location;

        retval = (tbd) d_dlist;
        if ((tbd) _for_each(s_dlist, start_location, end_location,
                            num, _for_each_copy_item,
                            (void *) &callback_data) == NULL) {
            retval = NULL;
        }
    }
end:
    return(retval);
}

typedef struct move_callback_data_s {
    tbd      d_dlist;
    tbd_item d_location;
} *move_callback_data;

void *_for_each_move_item(tbd      source_in,
                          tbd_item s_location,
                          void *   data_in)
{
    tbd                source  = NULL;
    void *             retval = NULL;
    move_callback_data data = (move_callback_data) data_in;

    if ( (source = check_tbd(source_in)) ) {
        // _for_each only gives us non-NULL locations:
        // unlink from source:
        if (s_location->prev) {
            s_location->prev->next = s_location->next;
        } else {
            source->first = s_location->next;
        }
        if (s_location->next) s_location->next->prev = s_location->prev;

        // link to destination
        s_location->prev = data->d_location;
        if (data->d_location) {
            s_location->next = data->d_location->next;
            if (data->d_location->next) {
                data->d_location->next->prev = s_location;
            }
            data->d_location->next = s_location;
        } else {
            s_location->next = data->d_dlist->first;
            data->d_dlist->first = s_location;
        }
        data->d_location = s_location;
        retval = data;
    }
    return(retval);
}

tbd tbd_move_items(tbd            d_dlist_in,
                   tbd_item       d_location_in,
                   const tbd      s_dlist_in,
                   const tbd_item start_location,
                   const tbd_item end_location,
                   int            num)
{
    tbd                         d_dlist;
    tbd                         s_dlist;
    tbd_item                    d_location;
    tbd                         retval = NULL;
    struct move_callback_data_s callback_data;
    
    if ( (s_dlist = check_tbd(s_dlist_in)) ) {
        d_location = d_location_in;
        if ( (d_dlist = check_tbd(d_dlist_in)) == NULL ) {
            d_dlist = _tbd_copy(s_dlist);
            d_location = NULL;
        } else {
            if (s_dlist->copy_callback != d_dlist->copy_callback ||
                s_dlist->create_callback != d_dlist->create_callback ||
                s_dlist->free_callback != d_dlist->free_callback)
                goto end;
        }

        callback_data.d_dlist = d_dlist;
        callback_data.d_location = d_location;

        retval = (tbd) d_dlist;
        if ((tbd) _for_each(s_dlist, start_location, end_location,
                            num, _for_each_move_item,
                            (void *) &callback_data) == NULL) {
            retval = NULL;
        }
    }

end:
    return(retval);
}

tbd_item tbd_push(tbd *   dlist_in, 
                  void *  payload)
{
    tbd      dlist = NULL;
    tbd_item item = NULL;
    tbd_item last = NULL;
    tbd_item retval = NULL;
    
    if (dlist_in == NULL) goto end;
    
    if (*dlist_in == NULL) {
        dlist = tbd_new(0, NULL, NULL, NULL, NULL);
    } else {
        if ( (dlist = check_tbd(*dlist_in)) == NULL) {
            goto end;
        }
    }
    // walk to the end of the list:
    for (last = NULL, item = dlist->first; item; item = item->next) {
        last = item;
    }

    retval = _tbd_append_new(dlist, last);
    retval->payload = payload;
    *dlist_in = (tbd) dlist;
    
end:
    return(retval);
}

tbd_item tbd_get_newest(const tbd dlist_in)
{
    tbd dlist;
    tbd_item iter;
    tbd_item retval = NULL;

    if ( (dlist = check_tbd(dlist_in)) ) {
        for (iter = dlist->first; iter; iter = tbd_get_next(iter)) {
            retval = iter;
        }
    }
    return(retval);
}

tbd_item tbd_get_oldest(const tbd dlist_in)
{
    tbd dlist;
    tbd_item retval = NULL;
    
    if ( (dlist = check_tbd(dlist_in)) ) {
        retval = dlist->first;
    }
    return(retval);
}

void *tbd_pop(const tbd dlist_in)
{
    tbd_item item;
    tbd dlist;
    void *retval = NULL;
    
    if ( (dlist = check_tbd(dlist_in)) ) {
        item = tbd_get_newest(dlist_in);
        if (item) {
            retval = item->payload;
            if (dlist->first == item) {
                dlist->first = NULL;
            } else {
                item->prev->next = NULL;
            }
            xfree(item);
        }
    }
    return(retval);
}

void *tbd_pop_oldest(const tbd dlist_in)
{
    tbd_item item;
    tbd dlist;
    void *retval = NULL;
    
    if ( (dlist = check_tbd(dlist_in)) ) {
        item = dlist->first;
        if (item) {
            retval = item->payload;
            dlist->first = item->next;
            if (dlist->first) dlist->first->prev = NULL;
            xfree(item);
        }
    }
    return(retval);
}

typedef struct _sort_callback_data_s {
    void **array;
    int index;
    int direction; // 0 for dlist to array
} *_sort_callback_data;


void *_for_each_sort_item(tbd      dlist,
                          tbd_item location,
                          void *         callback_data)
{
    _sort_callback_data data =
        (_sort_callback_data) callback_data;

    if (data->direction == 0) {
        // dlist to array:
        data->array[data->index++] = location->payload;
    } else {
        // array to dlist:
        location->payload = data->array[data->index++];
    }
    return((void *)dlist);
}

tbd tbd_sort(tbd dlist, tbd_item location,
             int num, tbd_sort_compare_t compare)
{
    tbd retval = NULL;
    struct _sort_callback_data_s callback_data;
    
    if ( check_tbd(dlist) ) {
        int count = num;
        
        if (num == 0) {
            count = tbd_get_len(dlist);
        } else if (num < 0) {
            count = -num;
        }
        callback_data.array =
            (void **)xcalloc(count, sizeof(void *));
        callback_data.direction = 0;
        callback_data.index = 0;
        if (_for_each(dlist, location, NULL, num, _for_each_sort_item,
                      (void *)&callback_data) == NULL) goto end;
        
        qsort(callback_data.array,
              callback_data.index,
              sizeof(void *), compare);
        callback_data.direction = 1;
        callback_data.index = 0;
        if (_for_each(dlist, location, NULL, num, _for_each_sort_item,
                      (void *)&callback_data) == NULL) goto end;
        retval = dlist;
    }
end:
    if (callback_data.array) xfree(callback_data.array);
    return(retval);
}
